#include "inn.h"
#include <stdio.h>
#include <stdlib.h>
/**
 * @brief 书写关于栈的基础知识
 * @param
 * @return
 */
/**
 * @brief 初始化栈，其实就是将栈顶指针设置为-1
 * @param
 * @return
 */
void InitStack(SeqStack *S)
{
    S->top = -1;
}
/**
 * @brief 判断栈是不是空的
 * @param
 * @return
 */
bool StackEmpty(SeqStack S)
{
    // 如果栈顶指针指向空就是一个空栈
    return S.top == -1;
}
/**
 * @brief 判断栈是不是满的
 * @param S 栈
 * @return 栈满返回true，否则返回false
 */
bool StackFull(SeqStack *S)
{
    // 判断栈满，其实就是判断栈顶指针是不是等于最大长度-1
    return S->top == MAXSIZE - 1;
}
/**
 * @brief 入栈其实是根据栈顶指针的移动，
 * 然后插入对应的元素，栈顶指针需要优先移动
 * @param S 栈
 * @param elem 压入的元素
 * @return 压入成功返回true，否则返回false
 */
bool Push(SeqStack *S, int elem)
{
    // step1 判断栈是不是满了
    // 这个S是一个结构体指针，所以需要使用*解引用
    if (StackFull(S))
    {
        printf("栈已满，无法入栈");
        return false;
    }
    // 栈顶指针先加加，然后在入栈
    int top_pointer = ++(S->top);
    S->data[top_pointer] = elem;
    return true;
}
bool Pop(SeqStack *S, int *elem)
{
    // 判断栈是不是空的
    if (StackEmpty(*S))
    {
        printf("栈已空，无法出栈");
        return false;
    }
    *elem = S->data[S->top--];
    return true;
}
bool GetTop(SeqStack S, int *elem)
{
    // 判断栈是不是空的
    if (StackEmpty(S))
    {
        printf("栈已空，无法获取栈顶元素");
        return false;
    }
    // 如果不是空的，直接将数组里边的元素赋值到*elem里边就可以了
    *elem = S.data[S.top];
    return true;
}
void PrintStack(SeqStack S)
{
    // 打印栈顶元素依然需要判断栈是不是空的
    if (StackEmpty(S))
    {
        printf("栈已空，无法打印栈");
        return;
    }
    printf("栈内容,从栈底开始:");
    for (int i = 0; i <= S.top; i++)
    {
        printf("%d  → ", S.data[i]);
    }
    printf("\n");
}

void ClearStack(SeqStack *S)
{
    // 清空栈直接将栈顶指针设置为-1
    S->top = -1;
}
int StackLength(SeqStack S)
{
    return S.top + 1;
}
void InitStack_link(LinkStack *S)
{
    // 链栈是空的时候，栈顶指针指向null
    *S = NULL;
}
bool StackEmpty_link(LinkStack S)
{
    // 判断链栈是不是空的，
    // 其实就是判断这个节点是不是null就知道了
    return S == NULL;
}
/**
 * @brief 使用链表的方式入栈，
 * @param
 * @return
 */
bool Push_link(LinkStack *S, int elem)
{
    // step1 申请一片内存空间
    StackNode *newNode =
        (StackNode *)malloc(sizeof(StackNode));
    if (!newNode)
    {
        printf("内存分配失败\n");
        return false;
    }
    // 如果分配成功了，链表的数据域装elem，
    // 新节点的指针域指向栈的栈顶
    newNode->data = elem;
    newNode->next = *S;
    // 栈顶指针指向新节点
    *S = newNode;
    return true;
}

bool Pop_link(LinkStack *S, int *elem)
{
    if (StackEmpty_link(*S))
    {
        printf("栈为空\n");
        return false;
    }
    // 临时保存栈顶节点
    StackNode *temp = *S;
    // 保存栈顶元素值
    *elem = temp->data;
    // 栈顶指针向下移动
    *S = (*S)->next;
    // 释放原栈顶节点
    free(temp);
    return true;
}

bool GetTop_link(LinkStack S, int *elem)
{
    if (StackEmpty_link(S))
    {
        printf("栈为空\n");
        return false;
    }
    *elem = S->data;
    return true;
}

void PrintStack_link(LinkStack S)
{
    if (StackEmpty_link(S))
    {
        printf("栈为空\n");
        return;
    }
    printf("\n");
    printf("栈中元素为：（从栈顶到栈底）\n");
    StackNode *p = S;
    while (p != NULL)
    {
        printf("%d → ", p->data);
        p = p->next;
    }
    printf("\n");
}

void ClearStack_link(LinkStack *S)
{
    StackNode *p = *S;
    while (p != NULL)
    {
        StackNode *temp = p;
        p = p->next;
        free(temp);
    }
    *S = NULL;
}

int StackLength_link(LinkStack S)
{
    int length = 0;
    StackNode *p = S;
    while (p != NULL)
    {
        length++;
        p = p->next;
    }
    return length;
}